Numerous systems have been developed to overcome the complexity of determining when training and transition is to occur, and for which crew members, at which locations, at what times, and with an appropriate allocation of training resources including equipment and instructors.
The prior art systems have included both manual and automated systems with response times ranging from days, to weeks, and even months. Further, such systems have tended to implement a decision making process for providing a single solution, rather than a dynamic, adaptive, decision support system providing alternative solutions for evaluation by a strategic planner. In addition, such prior systems have been represented by models which either are too complex for commercial software solution, or have simplifying assumptions that make them too unrealistic for practical use. Prior systems also have generally been too costly in employee and equipment resources. See “Decision Support Systems-An application in strategic manpower planning of airline pilots” by Peter J. Verbeek, European Journal of Operational Research 55 (1991), pages 368-381, Elsevier Science Publishers B.V. While the Verbeek article does not disclose a decision support system, it does describe the enormous complexities which must be addressed in designing such a system to accommodate the large numbers of constraints and variables that are required for a solution to be realistic. A reference is made in the article to mixed integer models solved by linear programming (LP) which were developed by United Airlines and American Airlines, but fell short of being both realistic and optimal. Verbeek also referred to his own mixed integer model which was admittedly to complex for solution with commercial software, and thus too costly in time.
The article, “Course Planning at Lufthansa Technical Training: Constructing More Profitable Schedules”, by Knut Haase, Jorg Latteier, and Andreas Schirmer, INTERFACES 29:5 September-October 1999 (pp. 95-109) likewise does not disclose a specific model, but rather describes the enormity of the problems faced in attempting to design and develop a decision support system which can accommodate continuing data input changes while realizing reduced costs in creating training plans. No indication of creating and placing comparative values on alternative plans to generate multiple training plan options is indicated. Further, no indication of turnaround time is provided.
From the above it may be discerned that the problem of pilot staffing and training is one of the most complex and costly problems facing the major airlines. If not managed effectively, an airline cannot survive, not to mention profit, in the competitive air transportation market.
By way of example, Continental airlines provides both domestic and international service to more than 100 destinations around the world. They operate 325 aircraft of nine different fleet types to fly 1400 daily flights. Their 5000 pilots are stationed at three domestic and two international crew bases. At least twice a year Continental conducts a system bid award. These awards provide an opportunity for pilots to use their seniority to increase their pay and improve their work schedules by changing their position (base, fleet, and status), and a way for the airline to adjust staffing levels in response to retirements, attrition, and changes in their business plan. In an average system bid award, 15-20% of the airline's pilots receive new positions. The problem of taking the 15-20% of Continental's pilots who have received new positions, and finding a training class for each pilot requiring training, an advancement date for each pilot changing position without training, and a release date for each pilot leaving the airline is a very large NP-hard problem which must be solved. Additional complexity for Continental comes from the facts that: pilot positions are interrelated; the timing and number of training classes is variable; minimal length student training schedules must be generated using limited resources; and numerous complicating regulations and business rules related to each pilot's seniority, flight history, and current and future position must be considered.
Continental manpower planners with expert knowledge took more than two weeks to manually generate a single, partial, sub-optimal training plan for ensuring adequate staffing levels with no detailed consideration of costs.
In contrast to prior systems and methods, the invention described and claimed herein is a realistic representation of the real world problem as evidenced by its implementation by Continental Airlines, and is modeled so efficiently that it can be solved in under an hour. An hour is a huge improvement over the time required by the prior art systems, and is a very reasonable amount of time for a planning problem as complex as the one addressed by this invention.
The invention as described herein has been developed by CALEB Technologies Corp. of Austin, Tex., as part of an integrated decision support system, referred to as the ManpowerSolver system, to face this challenge. The ManpowerSolver system manages large volumes of data and employs state-of-the-art optimization modeling and solution techniques to efficiently allocate human and training resources, and attain optimal operational and cost effective performance.
In response to a system bid award, the ManpowerSolver system in accordance with the invention builds a training plan that establishes the timing and number of pilot new hires, training assignments, advancements, and releases. It also determines the number of pilots whose training or release should be postponed, and the flow of pilots across different positions in a manner that ensures adequate staffing levels, minimum cost, and efficient utilization of training resources.
By exercising different parameter settings, multiple high-quality solutions are generated that can be carefully examined before a suitable one is chosen by the user. The substantial time and process savings, however, are dwarfed by the savings derived from implementing an optimized solution that not only provides complete coverage of flights, but also significant dollar savings from reduced staffing costs, pay protection costs, and training costs. Staffing cost savings come from decreases in the number of new pilots hired, postponement of new pilot hires, quicker release of pilots without an award, and providing just-in-time training to minimize pilots being trained long before they are needed. Training cost savings arise from better utilization of expensive resources, reduced time for pilots to complete training, and a reduction in the number of training cycles required. Overall, Continental has estimated a dollar savings in excess of $10 million annually.
The primary objective of the training plans produced by the invention described and claimed herein is to have pilots in place at each combination of base (assigned geography), fleet, and status (seat) to cover all of the published flights. Secondary objectives include minimizing staffing, pay protection, and training and hiring costs. Constraints that are considered include pilot vacations and absences, available training resources, new hires, seniority, and training policies.
To solve the pilot training and transitioning (staffing) problem the ManpowerSolver system relies on a loosely coupled solution methodology that employs a unique combination of modeling and algorithmic approaches. Innovative aspects of this methodology include a decomposition of the problem into a series of linear and mixed integer programs, and a specialized branch and bound algorithm with custom branch ordering and node bounding techniques. Alternative cost effective training plans are produced and evaluated for selection of the training plan deemed most suitable to the airline.
The system can also be used in a what-if mode to gauge the impact that various operating decisions will have on pilot staffing and training. This tool allows crew planners to be proactive as they face changes in the airline such as new market opportunities, the acquisition and retirement of aircraft and training resources, opening and closing sub-bases, and modification to the number of hours to be flown from different pilot positions to allow the airline to take advantage of business opportunities.
This integrated approach to workforce management that takes into account the broad spectrum of hiring, staffing, training, and absence is the first in the airline industry. The concept and framework as well as some of the solution techniques are general enough to be applied to industries other than airlines that desire a skilled workforce.